<!-- 分治法-快速排序-随机基准 -->
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>分治法-快速排序-随机基准</title>
    <script type="text/javascript" src="jquery-1.7.2.min.js"></script>
	<script>
        var a=[];
        var b=[];
        var k=0;
        function indexOf (b,x,p,q)
    { 
        for (var i = p; i <=q; i++) { 
        if (b[i] == x) return i; 
        } 
        return -1;
    }
        function re (b,y) 
        { 
         b[y]=-100000;
        };
		function swap(a,i,j)     //两元素进行交换
	{                  
		var temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
	function partition(a,p,q)    //进行分区算法设计
    {   var x=a[p];              
		var i=p,j;
		for(j=p+1;j<=q;j++)
		{
			if(a[j]<=x)
			{
				i++; 
				swap(a,i,j); 
			}
		}
		swap(a,p,i);
        $("#sort").append("基准："+x+";r="+i+";arr="+a+";p="+p+"; q="+q+"<br/>");  //打印每次递归的的各变量数据，调用了jq库
		return i;
        
	}
	function quicksort(a,p,q)     //递归的调用     
	{
		if(p<q)
		{   
            var d=parseInt(Math.random()*(q-p+1)+p); //随机基准
            swap(a,p,d);      //分区首地址与随机基准地址进行调换
            var r=partition(a,p,q);  
			quicksort(a,p,r-1);
			quicksort(a,r+1,q);
		}  
	}	
	function  quicksort1()
	{   document.getElementById("sort").innerHTML="";   //该代码可使html里盒模型的内容清空，做到多次排序时数据不会叠加
		a=document.getElementById("arr1").value.split(",");//把网页文本框输入的数组转换成字符数组
		for(var i=0;i<a.length;i++)//把字符数组转换成整型数组，从而做到可排序
		{
			a[i]=parseInt(a[i]);
        }
		   quicksort(a,0,a.length-1);
           $("#sort").append("最终结果："+a); //输出最终结果
	}
	</script>
	<style>
		body
		{
			background-color: antiquewhite;
			margin: 0;
			text-align:center

		}
		.d1
		{
			border:1px solid red;
			width:500px;
			height:300px;
			margin:0  auto;
			text-align:left;
			padding-left:0;
			
		}
		#sort /*结果*/
		{   
			color: blue;
		}
	</style>
</head>
<body >
	数据：
  <input type="text" name="arr1" id="arr1" style="width:600px" value=""/>
  <p>如：7,3,4,90,3,20,8,201 注意：元素间的分隔号为英文逗号</p>
	<br/>
    <input type="button" value="快速排序-随机基准" onclick="quicksort1()" />
	<br/>
	排序结果：
	<div class="d1" id="sort">
	</div>
</body>
</html>